package com.example.programmerinterview;

import com.example.structure.ListNode;

/**
 * 面试题 02.04. 分割链表
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * <p>
 * 你不需要 保留 每个分区中各节点的初始相对位置。
 * <p>
 * 示例 1：
 * <p>
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 * 思路：不要想太复杂！！就是用两个链表接受然后再合到一起
 */
public class Partition {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy = new ListNode(0);
        ListNode small = dummy;
        ListNode maxPre = new ListNode(0);
        ListNode max = maxPre;
        while (head != null) {
            if (head.val < x) {
                small.next = new ListNode(head.val);
                small = small.next;
            } else {
                max.next = new ListNode(head.val);
                max = max.next;
            }
            head = head.next;
        }
        small.next = maxPre.next;
        return dummy.next;
    }
}
